// https://leetcode.cn/problems/merge-two-sorted-lists/description/

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

// 算法思路总结：
// 1. 递归合并两个有序链表
// 2. 比较两个链表头节点值，选择较小者作为当前节点
// 3. 递归连接剩余部分的合并结果
// 4. 处理边界情况：任一链表为空时直接返回另一链表
// 5. 时间复杂度：O(m+n)，空间复杂度：O(m+n)（递归栈）

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* createLinkedList(const vector<int>& nums)
{
    if (nums.empty()) return nullptr;
    
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    
    for (int num : nums)
    {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

void printLinkedList(ListNode* head)
{
    if (!head)
    {
        cout << "空链表" << endl;
        return;
    }
    
    ListNode* cur = head;
    while (cur)
    {
        cout << cur->val;
        if (cur->next)
            cout << " -> ";
        else
            cout << " -> nullptr";
        cur = cur->next;
    }
    cout << endl;
}

class Solution 
{
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        if (l1->val < l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else 
        {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }

        return nullptr;    
    }
};

int main()
{
    vector<int> v1 = {1,2,4}, v2 = {1, 3, 4};
    Solution sol;

    auto l1 = createLinkedList(v1), l2 = createLinkedList(v2);

    auto r1 = sol.mergeTwoLists(l1, l2);
    printLinkedList(r1);


    return 0;
}

